            BOI.1.(Obiecte). Consider[m un tablou bidimensional A cu m linii i n
coloane (1m19,1n19) ale c[rui elemente sunt 0 i 1. 0 reprezint[ fondul
(paper), 1 reprezint[ culoarea tuului (ink).
           Pe tablou sunt reprezentate mai multe obiecte. Prin obiect vom nelege o
mulime de elemente cu acelai ink (1), fiecare element avnd cel puin un vecin
n stnga, dreapta, sus, jos sau pe una din diagonale. Orice dou[ obiecte sunt
separate prin elemente de tipul 0 (paper).
           a) S[ se determine dreptunghiul de arie minim[ care conine un obiect
maximal (avnd cel mai mare num[r de elemente 1).
           b) S[ se plaseze obiectul aflat la punctul (a) n zonele tabloului care nu sunt
ocupate de alte obiecte, n aa fel nct copierea lui s[ se poat[ face n ct mai
multe locuri posibile f[r[ a distruge celelalte obiecte deja plasate.
Exemplu:
                                                       0  0  0  0  0  0  0  1  1  0
                                                          0  1  0  0  1  1  0  1  1  1     obiect
                                                          0  0  1  0  1  1  0  0  0  1
                                                          0  0  0  0  1  1  1  0  0  1
                                                          0  0  1  1  1  1  1  0  0  0
                                                          0  0  1  1  1  1  1  0  1  1
obiect maximal             1  1  1  1  1  0  0  0  1  1
                                                          0  0  0  1  0  0  0  0  1  1
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0
                                                          0  0  0  0  0  0  0  0  0  0

                                                          plasare posibil[

==========================================================
BOI 1 (Adrian Atanasiu):
           Rezolvarea problemei se bazeaz[ pe urm[toarele idei:
  - n culoare se determin[ un obiect necolorat (primul element notat cu 1);
  - se pune pe acest element o culoare nou[;
  - se trimite la pata, care coloreaz[ cu aceeai culoare tot obiectul; pentru a scrie
mai uor algoritmul, tabloul a a fost bordat cu cte o linie i o coloan[ suplimentare
umplute cu 0;
  - procedeul se repet[ pn[ nu se mai g[sesc obiecte necolorate (toate elementele
tabloului sunt diferite de 1).
Se trece apoi la rezolvarea punctului (a) folosind procedura dreptunghi, anume:
   - se g[sete culoarea care predomin[ n tablou; ea aparne obiectului de m[rime
maxim[ i este reinut[ n variabila fond;
  - se determin[ punctele cu aceast[ culoare care au coordonate extreme: cei mai
mici si cei mai mari x i y; prin aceste puncte vor trece laturile dreptunghiului.
Observaie: S-a presupus c[ este vorba de un dreptunghi cu laturile paralele cu
axele de coordonate.
   Pentru rezolvarea punctului (b) se folosete procedura plasare; ea aduce prin
intermediul tabloului model, copii ale obiectului maximal n toate poziiile i veri-
fic[ dac[ ele pot fi aezate n tablou f[r[ a se suprapune cu altele.
   Procedura mutare asigur[ diverse poziii ale obiectului.
In final se p[streaz[ tabloul n care au putut fi introduse un num[r maxim de copii.
program obiecte;
uses crt;
var
 a:array[0..20,0..20] of integer; {a se bordeaza cu elemente 0}
  b,model:array[1..19,1..19] of integer;
  m,n,i,j,culoare,fond:integer;
  minx,miny,maxx,maxy,x1,y1:integer;
  s:boolean;
------------------------------------------------
procedure pata;
{marcheaza cu culoare tot obiectul insemnat}
var
  ii,jj,k1,k2:integer;
  vecin:boolean;
begin
  repeat
  vecin:=false;
  for ii:=1 to m do
    for jj:=1 to n do
      if a[ii,jj]=culoare then
         for k1:=ii-1 to ii+1 do
            for k2:=jj-1 to jj+1 do
              if a[k1,k2]=1 then begin
a[k1,k2]:=culoare;vecin:=true end
  until vecin=false
end;
--------------------------------------------------
procedure marcaj;
{se delimiteaza obiectele, marcand fiecare obiect printr-un
numar supraunitar}
begin
   culoare:=1;
   for i:=1 to m do
     for j:=1 to n do
        if a[i,j]=1 then begin
          culoare:=culoare+1; a[i,j]:=culoare;
          pata end
end;
------------------------------------------------------
procedure dreptunghi;
{se determina cel mai mare obiect si se incadreaza intr-un
dreptunghi}
var
  max,obj,r,s:integer;
begin
  max:=0; fond:=0;
  for i:=2 to culoare do begin
    obj:=0;
    for r:=1 to m do
      for s:=1 to n do
         if a[r,s]=i then obj:=obj+1;
    if max<obj then begin max:=obj;fond:=i end
                        end;
  {obiectul maxim are culoarea i retinuta din fond}
  {se determina acum coordonatele extreme ale obiectului
maximal}
  minx:=m;miny:=n;maxx:=1;maxy:=1;
  for r:=1 to m do
     for s:=1 to n do
       if a[r,s]=fond then begin
           if minx>r then minx:=r;
           if maxx<r then maxx:=r;
           if miny>s then miny:=s;
           if maxy<s then maxy:=s end;
  writeln('Obiectul maximal este cuprins in dreptunghiul de
varfuri:');
  writeln('(',minx,',',miny,')  (',maxx,',',miny,') 
(',maxx,',',maxy,')  (',minx,',',maxy,')');
end;
-------------------------------------------------------
procedure mutare;
var
  im,ii,wx,wy,jm,jj:integer;
begin
  im:=1;jm:=0;s:=true;
  wx:=m-maxx+minx;wy:=n-maxy+miny;
    repeat
    jm:=jm+1;
    if jm>wy then begin im:=im+1; jm:=1 end;
  until b[im,jm]=1;
  for ii:=1 to m do
    for jj:=1 to n do b[ii,jj]:=0;
{deplasarea obiectului in b. Daca a fost posibila deplasarea
s:=false; daca deplasarea nu a fost posibila, s:=true si
obiectul se rearanjeaza la pozitia initiala, cu coltul din
stanga sus pe (x1,y1+1) sau (x1+1,y1)}
  if (im=wx) and (jm=wy) then begin
     for ii:=1 to maxx-minx+1 do
       for jj:=1 to maxy-miny+1 do
         if y1<wy then b[x1+ii-1,y1+jj]:=model[ii,jj]
     else if x1<wx then  b[x1+ii,y1+jj-1]:=model[ii,jj] end
         else begin
       for ii:=1 to maxx-minx+1 do
         for jj:=1 to maxy-miny+1 do
             if jm<wy then begin 
                           s:=false; b[im+ii-1,jm+jj]:=model[ii,jj] end
                      else b[x1+ii,y1+jj-1]:=model[ii,jj]
                      end
end;
---------------------------------------------------------------
procedure plasare;
var
  c,final:array[1..19,1..19] of integer;
  suprapus:boolean;
  p,maxobj:integer;
begin
  for i:=1 to m do
     for j:=1 to n do begin
        if a[i,j]=fond then b[i-minx+1,j-miny+1]:=1
                       else b[i-minx+1,j-miny+1]:=0;
        if a[i,j]>0 then a[i,j]:=1;
                     end;
  for i:=0 to maxx-minx do
    for j:=0 to maxy-miny do model[i+1,j+1]:=b[i+1,j+1];
  maxobj:=0;
  for x1:=1 to m-maxx+minx do
    for y1:=1 to n-maxy+miny do begin
      p:=0;
      for i:=1 to m do
        for j:=1 to n do c[i,j]:=a[i,j];
  repeat
    suprapus:=false;
    for i:=1 to m do
       for j:=1 to n do begin
          c[i,j]:=c[i,j]+b[i,j];
          if c[i,j]=2 then suprapus:=true end;
    if suprapus then
       for i:=1 to m do
          for j:=1 to n do c[i,j]:=c[i,j]-b[i,j]
                else p:=p+1;
    mutare
    until s;
  if maxobj<p then begin
     maxobj:=p;
     for i:=1 to m do
        for j:=1 to n do final[i,j]:=c[i,j]
                   end;
                         end;
  writeln('Noua configuratie contine ',maxobj, ' copii ale
obiectului maximal:');
  for i:=1 to m do begin
     for j:=1 to n do write(final[i,j],' ');
     writeln end;
end;
----------------------------------------------------------------
begin {program principal}
  clrscr;
  write('dati dimensiunile tabloului: ');readln(m,n);
  writeln('dati elementele tabloului:');
  for i:=0 to 20 do
     for j:=0 to 20 do a[i,j]:=0;
  for i:=1 to m do begin
    for j:=1 to n do read(a[i,j]);
    readln end;
  marcaj;
    writeln('Obiectele marcate sunt:');
  for i:=1 to m do begin
    for j:=1 to n do write(a[i,j],'  ');
    writeln end;
  dreptunghi;
  plasare
end.
---------------------------------------
            BOI.1. (Vlad Atanasiu)
Programul a fost construit cu preciz[ri comentate pentru a urm[ri uor algoritmul
folosit.
uses crt;
type punct=record
           x,y:integer;
           end;
     list=^lst;
     lst=record
         p:punct;
         urm:list;
         end;
     cap_lista=^caplista;
     caplista=record
               nr_puncte:integer;
               urm:cap_lista;
               lista:list;
               end;
     grila=record
                 tb:array[1..100,1..100] of byte;
                 dimx,dimy:integer;
           end;
var minx,maxx,miny,maxy,arie_min,nrmaxim,i,j:integer;
    tablou:grila;
    cmm,primalista,cl,cap:cap_lista;
    pct:punct;
-------------------------------------------------------
function trebuie_adaugat(l:list;c:punct):boolean;
          {Intoarce true daca punctul are un vecin in lista L}
var tmp:boolean;
begin
   tmp:=false;
   while (l<>nil) and (not tmp) do
      if (abs(l^.p.x-c.x)<2) and (abs(l^.p.y-c.y)<2) 
           then tmp:=true else l:=l^.urm;
   trebuie_adaugat:=tmp;
end;
---------------------------------------------------------
procedure adauga_punct(var l:cap_lista;c:punct);
{ Adauga un punct la o lista si mareste nrmaxim daca
nrpuncte>nrmaxim atunci nrmaxim=nrpuncte }
var listatmp:list;
begin
   listatmp:=l^.lista; new(l^.lista);
   l^.lista^.p:=c; l^.lista^.urm:=listatmp;
   inc(l^.nr_puncte);
   if l^.nr_puncte>nrmaxim then nrmaxim:=l^.nr_puncte;
end;
---------------------------------------------------------------
procedure afiseaza_lista(cl:cap_lista);
var f:list;
begin
   f:=cl^.lista;
   while f<>nil do
      begin
         write('(',f^.p.x,',',f^.p.y,')');
         f:=f^.urm;
      end;
   writeln('are ',cl^.nr_puncte,' puncte. ');
end;
--------------------------------------------------------
procedure reuniune(var lista1,lista2:cap_lista);
{ Adauga lista2 la lista1 si sterge lista2 }
var listatmp:list;
begin
   listatmp:=lista1^.lista;
   if listatmp<>nil then while listatmp^.urm<>nil do
      listatmp:=listatmp^.urm;
   listatmp^.urm:=lista2^.lista;
   lista1^.nr_puncte:=lista1^.nr_puncte+lista2^.nr_puncte;
   lista2^.lista:=nil;
   lista2^.nr_puncte:=0;
   if lista1^.nr_puncte>nrmaxim then nrmaxim:=lista1^.nr_puncte;
end;
-------------------------------------------------------
procedure citeste(var g:grila);
{Se citeste grila, pe coloane. Cand se va face referire la un
punct, prima coordonate data va fi y si dupa aceea x}
var input:text;
   i,j:integer;
   s:string;
begin
   assign(input,'input');
   reset(input);
   readln(input,g.dimx,g.dimy);
   for i:=1 to g.dimy do
      begin
         for j:=1 to g.dimx do read(input,g.tb[i,j]);
         readln(input);
      end;
   close(input);
end;
---------------------------------------------------------
procedure afiseaza(var g:grila);
var i,j:integer;
begin
   writeln('Dim.: ',g.dimy,' linii, ',g.dimx,'coloane.');
   for i:=1 to g.dimy do
      begin
         for j:=1 to g.dimx do write(g.tb[i,j],' ');
         writeln;
      end;
end;
--------------------------------------------------
procedure init_cap_lista(var cl:cap_lista);
begin
   cl:=new(cap_lista);
   cl^.nr_puncte:=0; cl^.lista:=nil; cl^.urm:=nil;
end;
----------------------------------------------------
function arie(l:list):integer; 
{functia intoarce arie dreptunghiului care poate incadra  
obiectul din lista l }
begin
   minx:=l^.p.x; miny:=l^.p.y; maxx:=l^.p.x; maxy:=l^.p.y;
   while l<>nil do
      begin
        if l^.p.x>maxx then maxx:=l^.p.x;
        if l^.p.x<minx then minx:=l^.p.x;
        if l^.p.y>maxy then maxy:=l^.p.y;
        if l^.p.y<miny then miny:=l^.p.y;
        l:=l^.urm;
      end;
   arie:=(maxx-minx+1)*(maxy-miny+1);
end;

function se_poate(i,j:integer):boolean;
{ functia intoarce True daca la coordonatele i,j se poate pune
obiectul maximal fara sa altereze alte obiecte deja existente.}
var l:list; sepoate:boolean;
begin
   l:=cmm^.lista; sepoate:=true;
   while (l<>nil) and (sepoate) do
      begin
    if f^tablou.tb[l^.p.y-miny+i,l^.p.x-minx+j]=1 
       then sepoate:=false; l:=l^.urm;
      end;
   se_poate:=sepoate;
end;
---------------------------------------------------------
procedure aseaza(i,j:integer);
{ pune obiectul maximal in grila la pozitia i,j }
var l:list;
begin
   l:=cmm^.lista;
   while l<>nil do
      begin
        tablou.tb[l^.p.y-miny+i,l^.p.x-minx+j]:=1;
        l:=l^.urm;
      end;
end;
------------------------------------------------------
begin { PROGRAMUL PRINCIPAL }
   clrscr;
   cap:=nil; nrmaxim:=0;
   citeste(tablou);
      { pentru fiecare punct }
   for pct.y:=1 to tablou.dimy do for pct.x:=1 to
      tablou.dimx do
       { daca este 1 atunci }
     if tablou.tb[pct.y,pct.x]=1 then
        begin
           primalista:=nil; 
{ punctul inca nu a fost adaugat nicaieri, asa ca prima lista
in care va fi adaugat nu e inca cunoscuta }
            { pentru fiecare cap_lista }
           cl:=cap;
           while cl<>nil do
              begin
             { daca trebuie adaugat in lista respectiva }
                if trebuie_adaugat(cl^.lista,pct) then
                   begin
{ daca inca nu a fost adaugat nicaieri prima lista ia         
 valoarea listei curente}
                     if primalista=nil then
                        begin
                           primalista:=cl;
{ daca lista curenta nu este prima lista la care a fost
  adaugat punctul, o concateneaza cu prima lista }
{ adauga punct la doar la prima lista }
                           adauga_punct(cl,pct);
                        end
                          else reuniune(primalista,cl);
                   end;
                cl:=cl^.urm;
              end;
            { daca nu a fost adaugat la nici o lista }
            if primalista=nil then
               begin
{se creeaza un nou cap_lista care contine o lista }
                 cl:=cap; init_cap_lista(cap);
                 cap^.urm:=cl;
{ adauga_punct la lista nou creeata }
                 adauga_punct(cap,pct);
              end;
            end;
   cl:=cap;
{ vom inmagazina in cmm pointerul spre obiectul cu cel mai    
mare numar de elemente si care este incadrat intr-un
   dreptunghi de arie minima }
   cmm:=cap; arie_min:=tablou.dimx*tablou.dimy;
{ pentru fiecare obiect }
   while cl<>nil do
      begin
{ daca numarul de elemente este maxim si aria obiectului
    este mai mica decat aria minima }
       if (cl^.nr_puncte=nrmaxim) and 
          (arie(cl^.lista)<arie_min) then
          begin
{ reactualizeaza variabilele }
             cmm:=cl; arie_min:=arie(cl^.lista);
          end;
       cl:=cl^.urm;
     end;
   writeln('Obiectul cautat este ');
   afiseaza_lista(cmm);
   writeln('Poate fi incadrat intr-un dreptunghi cu aria
           de',arie_min,' puncte.');
   write('Asezarea optima a obiectului: ');
   for i:=1 to tablou.dimy-maxy+miny do
      for j:=1 to tablou.dimx-maxx+minx do
         if se_poate(i,j) then
            begin
              write('(',i,',',j,')'); aseaza(i,j);
            end;
   writeln; writeln('Grila a devenit :');afiseaza(tablou);
end.
------------------------------------------
